package arithmetic.dynamicprogramming;

/**
 * 这段代码是一个计算问题，旨在计算给定条件下的不同方式的数量。具体来说，它是在解决一个类似于“投掷骰子”的问题，其中我们要计算使用n个骰子得到总和为x的不同方式的数量。
 *
 * 让我们逐步解释代码：
 *
 * 输入参数:
 *
 * m: 骰子的面数（通常是6，因为一个标准的骰子有6面）。
 * n: 投掷的骰子数量。
 * x: 投掷后希望得到的总和。
 * 初始化表格:
 * 代码创建了一个二维数组table来存储子问题的结果。这个表格的大小是(n + 1) x (x + 1)，并且使用骰子的数量作为行索引，总和作为列索引。
 *
 * 初始化单骰子的结果:
 * 对于只有一个骰子的情况，如果其总和为j（其中j从1到m），那么只有一种投掷方式。所以，代码为每一个这样的j设置table[1][j] = 1。
 *
 * 填充表格:
 * 对于多于一个骰子的情况，我们需要使用递归关系来填充表格。对于i个骰子（其中i从2到n）和总和为j（其中j从1到x），我们遍历所有可能的骰子的面数（从1到j-1且不超过m），并累加之前的结果（即减去当前面数的结果）。
 *
 * 返回结果:
 * 最后，返回表格中table[n][x]的值，即使用n个骰子得到总和为x的不同方式的数量。
 *
 * 总的来说，这段代码使用动态规划的方法来计算投掷骰子的不同方式的数量。
 */
class DP {
    public static long findWays(int m, int n, int x) {

        long[][] table = new long[n + 1][x + 1];

        for (int j = 1; j <= m && j <= x; j++) {
            table[1][j] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= x; j++) {
                for (int k = 1; k < j && k <= m; k++) {
                    table[i][j] += table[i - 1][j - k];
                }
            }
        }

        return table[n][x];
    }

    public static void main(String[] args) {
        System.out.println(findWays(4, 2, 1));
        System.out.println(findWays(2, 2, 3));
        System.out.println(findWays(6, 3, 8));
        System.out.println(findWays(4, 2, 5));
        System.out.println(findWays(4, 3, 5));
    }
}
/*
OUTPUT:
0
2
21
4
6
 */
// Time Complexity: O(m * n * x) where m is number of faces, n is number of dice and x is given sum.
